class CircularLinkedList:
    class _Node:
        def __init__(self, data, next):
            self._data = data
            self._next = next

    def __init__(self):
        self._tail = None  # We only keep track of tail; head is tail._next
        self._size = 0
    
    def __repr__(self):
        if self.is_empty():
            return "None"
        
        nodes = []
        current = self._tail._next  # Start from head
        for _ in range(self._size):
            nodes.append(current._data)
            current = current._next
        nodes.append(f"-> (back to {self._tail._next._data})")
        return " -> ".join(nodes)
    
    def __len__(self):
        return self._size
    
    def is_empty(self):
        return self._size == 0

    def get_head(self):
        return self._tail._next._data if self._tail is not None else 'Empty'
    
    def get_tail(self):
        return self._tail._data if self._tail is not None else 'Empty'

    def add_tail(self, e):
        """
        Add an element to the back of the tail
        """
        newest = self._Node(e, None)
        if self.is_empty():
            newest._next = newest  # Point to itself
            self._tail = newest
        else:
            newest._next = self._tail._next  # Point to head
            self._tail._next = newest
            self._tail = newest
        self._size += 1

    def pop_tail(self):
        """
        Remove and return the last element
        """
        if self.is_empty():
            raise Empty("It's Empty")
        
        answer = self._tail
        if self._size == 1:
            self._tail = None
        else:
            # Find the node before tail
            current = self._tail._next  # Start from head
            while current._next is not self._tail:
                current = current._next
            current._next = self._tail._next  # Point to head
            self._tail = current
        self._size -= 1
        return answer._data
    
    def pop_head(self):
        """
        Remove and return the first element
        """
        if self.is_empty():
            raise Empty("It's Empty")
        
        head = self._tail._next
        answer = head._data
        
        if self._size == 1:
            self._tail = None
        else:
            self._tail._next = head._next
        self._size -= 1
        return answer
    
    def add_head(self, e):
        """
        Add an element to the front of the head
        """
        newest = self._Node(e, None)
        if self.is_empty():
            newest._next = newest  # Point to itself
            self._tail = newest
        else:
            newest._next = self._tail._next  # Point to current head
            self._tail._next = newest
        self._size += 1
    
    def search(self, e):
        """
        Search for an element in the linked list
        """
        if self.is_empty():
            return False
        
        current = self._tail._next  # Start from head
        for _ in range(self._size):
            if current._data == e:
                return True
            current = current._next
        return False
    
    def rotate(self):
        """
        Rotate the list: move head to tail
        """
        if not self.is_empty():
            self._tail = self._tail._next
    
    def get_all_nodes(self):
        """
        Return a list of all node data in order
        """
        if self.is_empty():
            return []
        
        nodes = []
        current = self._tail._next  # Start from head
        for _ in range(self._size):
            nodes.append(current._data)
            current = current._next
        return nodes


class Empty(Exception):
    def __init__(self, *args):
        super().__init__(*args)


if __name__ == '__main__':
    cll = CircularLinkedList()

    cll.add_tail('pomme')
    cll.add_tail('banana')
    cll.add_tail('orange')
    cll.add_tail('kiwi')
    print(f"Size: {cll._size}")
    print(f"List: {cll}")
    print(f"Head: {cll.get_head()}")
    print(f"Tail: {cll.get_tail()}")
    
    print(f"\nPopping head: {cll.pop_head()}")
    print(f"After pop_head: {cll}")
    
    print(f"\nSearch 'banana': {cll.search('banana')}")
    print(f"Search 'pomme': {cll.search('pomme')}")
    
    print(f"\nRotating the list...")
    cll.rotate()
    print(f"After rotate: {cll}")
    print(f"New head: {cll.get_head()}")
    print(f"New tail: {cll.get_tail()}")
    
    print(f"\nAdding 'fraise' to head...")
    cll.add_head('fraise')
    print(f"After add_head: {cll}")
    
    print(f"\nAll nodes: {cll.get_all_nodes()}")
    
    print(f"\nPopping tail: {cll.pop_tail()}")
    print(f"After pop_tail: {cll}")
